package leetcode.每日一题;

import lombok.Data;
import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/6/20 9:17
 * @description：https://leetcode-cn.com/problems/throne-inheritance/
 */
public class 皇位继承顺序 {
    @Test
    public void test() {
        ThroneInheritance t = new ThroneInheritance("king");
        t.birth("king", "andy");
        t.birth("king", "bob");
        t.birth("king", "catherine");
        t.birth("andy", "matthew");
        t.birth("bob", "alex");
        t.birth("bob", "asha");
        System.out.println(t.getInheritanceOrder());
        t.death("bob");
        System.out.println(t.getInheritanceOrder());
    }

    class ThroneInheritance {

        private String king;

        Map<String, Person> map = new HashMap<>();

        public ThroneInheritance(String kingName) {
            map.put(kingName, new Person(kingName));
            king = kingName;
        }

        public void birth(String parentName, String childName) {
            Person child = new Person(childName);
            List<Person> children = map.get(parentName).children;
            children = children == null ? new ArrayList<>() : children;
            children.add(child);
            map.get(parentName).children = children;
            map.put(childName, child);
        }

        public void death(String name) {
            map.get(name).isDeath = true;
        }

        ArrayList<String> ans;
        public List<String> getInheritanceOrder() {
            //DFS
            ans = new ArrayList<>();
            Person cur = map.get(king);
            dfs(cur);
            return ans;
        }

        public void dfs(Person person) {
            if (!person.isDeath)
                ans.add(person.name);
            List<Person> children = person.children;
            if (children == null) return;
            for (Person child : children) {
                dfs(child);
            }
        }
    }

    class Person {
        public String name;
        public boolean isDeath;
        public List<Person> children;

        public Person(String name) {
            this.name = name;
        }
    }

/**
 * Your ThroneInheritance object will be instantiated and called as such:
 * ThroneInheritance obj = new ThroneInheritance(kingName);
 * obj.birth(parentName,childName);
 * obj.death(name);
 * List<String> param_3 = obj.getInheritanceOrder();
 */
}
